package com.rui.shangXueTang.binarySort;

/**
 * @author : [锐神NO.3]
 * @version : [v1.0]
 * @className : BinarySoryTree
 * @createTime : [2022/2/18 21:23]
 * @description : [二叉排序树]
 */

public class BinarySoryTree {

    private Node root;

    public Node getRoot() {
        return root;
    }

    public Node seleteByVal(int value){
        if(root == null){
            return null;
        }else {
            return root.selectByParent(value);
        }
    }

    /**
     * 查询父节点
     */
    public Node selectByParent(int value){
        if(root == null){
            return null;
        }else {
            return root.selectByParent(value);
        }
    }

    /**
     * 添加节点
     */
    public void add(Node node){
        if(root == null){
            root = node;
        }else {
            root.add(node);
        }
    }

    public void infixSelect(){
        if(root != null){
            root.infixSelect();
        }else {
            System.out.println("二叉树为空");
        }
    }

    /**
     * 删除节点
     * 如果删除的节点是叶子节点，找到父节点直接删除掉
     * 如果删除的节点带有左子树或者带有右子树，把左子树或者右子树的节点交给删除改节点的父节点
     */
    public void delNode(int value){
        if(root == null){
            return;
        }else {
            Node target = seleteByVal(value);
            if(target == null){
                return;
            }
            if(root.left == null && root.right == null){
                root = null;
            }

            //找到目标节点的父节点
            Node parent = selectByParent(value);

            //1.假设删除的是一个叶子节点
            if(target.left == null && target.right == null){
                //判断删除节点是父节点的左节点还是右节点
                if(parent.left != null && parent.left.value == value){
                    parent.left = null;
                }else if(parent.right != null && parent.right.value == value){
                    parent.right = null;
                }
            }else if(target.left != null && target.right != null){
                int minVal = rightTreeMin(target.right);
                target.value = minVal;
            }else {
                //删除只有一个子树，可能是右子树也可能是左子树
                if(target.left != null){
                    if(parent != null){
                        if(parent.left.value == value){
                            parent.left = target.left;
                        }else {
                            parent.right = target.left;
                        }
                    }else {
                        root = target.left;
                    }
                }else {
                    if(parent != null){
                        if(parent.left.value == value){
                            parent.left = target.right;
                        }else {
                            parent.right = target.right;
                        }
                    }else {
                        root = target.right;
                    }
                }
            }
        }
    }

    /**
     * 找出右子树的最小值
     */
    public int rightTreeMin(Node root){
        Node target = root;
        while(target.left != null){
            target = target.left;
        }
        delNode(target.value);
        return target.value;
    }
}
